#pragma once
#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <thread>
#include <mutex>
#include <unordered_map>
using std::cout;
using std::endl;
#ifdef _WIN32
#include<windows.h>
#else
// 
#endif
//函数和类用大驼峰，变量用小驼峰命名

/*
进程地址空间中有32位和64位的区分
32位下，假设每页8kb，即2^13，页数=2^32/2^13=2^19页；
64位下，假设每页8kb，即2^13, 页数=2^64/2^13=2^51页；
如果数量超过了int和size_t能表示的范围，64位可以用unsigned long long表示，范围为2^64-1；
32位如果也这么用会产生浪费，选择条件编译确定32位或者64位
_WIN32可以用来判断是否是Windows系统
_WIN64可以用来判断编译环境是否是（x64）64位还是（x86)32位
WIN32配置下，_WIN32有定义，_WIN64没有定义
WIN64配置下，两个都有定义
*/
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif

//申请的最大字节数256kb
static const size_t MAX_BYTES = 256 * 1024;
//自由链表桶的最大数
static const size_t FREE_LISTS = 208;
/*
单个对象最多256kb，page cache中有多少个桶取决于最大挂几页的span
这里设置最大128页，假设一页用的是8kb，128*8kb=1024kb,那么就可以切四段给central cache
为了让桶号与页号对应，可以将0号桶空着不用，因此将哈希桶的个数设置为129
*/
static const size_t NPAGES = 129;
//页大小转换偏移，一页定义为2^13，也就是8kb
static const size_t PAGE_SHIFT = 13;
//获取传入内存块的前4/8个字节,由于该函数被多个源文件使用，避免造成符号表冲突，static修饰
static void*& NextObj(void * obj)
{
    return *(void**)obj;
}
//直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}
//释放内存回堆
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    //linux下sbrk ummap等
#endif
}

//用模板的方式实现new和delete，同时增加定长内存池的特性，优化申请内存的性能
#define NUM 128*1024//大块内存大小 byte
template<class T> //T大小
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		//优先把还回来内存块对象，再次重复利用
		if (_freeList)
		{
			void* next = *((void**)_freeList);
			obj = (T*)_freeList;//obj需要强转一下，否则编译错误，强转是因为后续会解引用
			_freeList = next;
		}
		else
		{
			//剩余内存不够一个对象大小时，则重新开大块空间，bug：会最多浪费sizeof(T)-1个字节，造成内碎片（尽量避免）
			if (_remainBytes < sizeof(T))
			{
				_remainBytes = NUM;
				_memory = (char*)malloc(_remainBytes);//KB
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}

			obj = (T*)_memory;
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;
			_remainBytes -= objSize;
		}
		// 定位new, 显示调用T的构造函数初始化
		new(obj)T;

		return obj;
	}

	void Delete(T* obj)//bug：当回收到自由链表的内存块过多无法自动回收到系统(可修复)
	{
		//显示调用析构函数清理对象
		obj->~T();

		//头插
		*(void**)obj = _freeList;
		_freeList = obj;
	}
private:
	char* _memory = nullptr;//指向大块内存池的指针
	size_t _remainBytes = 0;//大块内存在切分过程中剩余的字节数
	void* _freeList = nullptr;//还回来过程中链接的自由链表的头指针
};

//自由链表
class FreeList
{
public:
    FreeList(){}
    ~FreeList(){}
    //头插
    void Push(void* obj)
    {
        assert(obj);
        NextObj(obj) = _freeList;
        _freeList = obj;
        _objNum++;
    }
    //头插多个内存块
    void PushRange(void* start, void* end, size_t objNum)
    {
        assert(start);
        assert(end);
        NextObj(end) = _freeList;
        _freeList = start;
        _objNum += objNum;
    }
    //头删
    void* Pop()
    {
        assert(_objNum > 0);
        void* obj = _freeList;
        _freeList = NextObj(obj);
        _objNum--;
        return obj;
    }
    void PopRange(void*& start, void*& end, size_t objNum)
    {
        assert(_objNum >= objNum);
        start = _freeList;
        end = start;
        //少走一个，把下一个给_freeList保存
        for(size_t i = 0; i < objNum - 1; i++)//第一轮循环执行语句后就已经给了2个内存块了
        {
            end = NextObj(end);
        }
        _freeList = NextObj(end);
        NextObj(end) = nullptr;
        _objNum -= objNum;
    }
    //如果自由链表桶里为空则为true，反之为false
    bool Empty()
    {
        return _freeList == nullptr;
    }
    //用于慢反馈调节算法
    size_t& MaxSize()
    {
        return _maxSize;
    }
    size_t Size()
    {
        return _objNum;
    }


private:
    void* _freeList = nullptr;
    size_t _maxSize = 1;//用于慢增长反馈调节
    size_t _objNum = 0;
};

//根据对象大小的对齐映射规则
class SizeClass
{
//该类只是为了对齐规则而制定，没有什么成员变量，通过static让其不必通过对象调用，并声明为内联函数减少栈帧开销
// 整体控制在最多10%左右的内碎片浪费
// [1,128] 8byte对齐    freelist[0,16)
// [128+1,1024] 16byte对齐  freelist[16,72)
// [1024+1,8*1024] 128byte对齐  freelist[72,128)
// [8*1024+1,64*1024] 1024byte对齐   freelist[128,184)
// [64*1024+1,256*1024] 8*1024byte对齐  freelist[184,208)
public:
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        /*
        size_t alignSize;
        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else
        {
            alignSize = size;
        }
        return alignSize;
        */
        //大佬写法
        return (((size)+alignNum - 1) & ~(alignNum - 1));
    }
    //计算对齐后所需要的字节数
    static inline size_t RoundUp(size_t size)
    {
        assert(size > 0);
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 1024 * 8)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 1024 * 64)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 1024 * 256)
		{
			return _RoundUp(size, 1024*8);
		}
		else
		{
			//大于256kb的按照页对齐
            return _RoundUp(size, 1 << PAGE_SHIFT);
		}
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        /*
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else
        {
            return size / alignNum;
        }
        */
        //大佬写法
        return((size + (1 << alignNum) - 1) >> alignNum) - 1;
    }

    //计算映射到哪个自由链表桶
    static inline size_t Index(size_t size)
    {
        assert(size > 0);
        //前四个分区的自由链表桶数
        static int groupArray[4] = {16, 56, 56, 56};
        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if (size <= 1024) 
        {
			return _Index(size - 128, 16) + groupArray[0];
		}
		else if (size <= 8 * 1024) 
        {
			return _Index(size - 1024, 128) + groupArray[1] + groupArray[0];
		}
		else if (size <= 64 * 1024) 
        {
			return _Index(size - 8 * 1024, 1024) + groupArray[2] + groupArray[1] + groupArray[0];
		}
		else if (size <= 256 * 1024) 
        {
			return _Index(size - 64 * 1024, 8 * 1024) + groupArray[3] + groupArray[2] + groupArray[1] + groupArray[0];
		}
		else 
        {
			assert(false);
            return -1;
		}
    }

    //一次thread cache从central cache获取多少个内存对象,慢反馈
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);
        //size越大计算的上限越低，反之则越高
        int num = MAX_BYTES / size;
        if(num < 2)
        {
            num = 2;//大于128kb，一次性给两个
        }
        if(num > 512)
        {
            num = 512;//小于512byte，一次性给512个
        }
        return num;
    }
    //将申请的size大小转化为页数
    static size_t NumMovePage(size_t size)
    {
        size_t num = NumMoveSize(size);//计算thread cache一次向central cache申请对象个数上限
        size_t nPage = num * size;//num个size大小的对象总的字节数
        nPage >>= PAGE_SHIFT;//字节数转换为页数
        if(nPage == 0)//至少给一页
        {
            nPage = 1;
        }
        return nPage;
    }
};

//管理多个连续大块页内存的结构体
struct Span
{
    PAGE_ID _pageId = 0;//起始页的页号
    size_t  _num = 0;//页数
    Span* _next = nullptr; //双向链表后指针
    Span* _pre = nullptr;//前指针
    size_t _useCount = 0 ;//小块内存分配计数
    size_t _objSize = 0;//切好的小块内存大小
    void*  _freeList = nullptr;//小块内存的自由链表
    bool _isUse = false;//是否在被使用
};
//带头双向循环链表
class SpanList
{
public:
    //链表头生成并初始化
    SpanList()
    {
        _head = _spanPool.New() ;
        _head->_next = _head;
        _head->_pre = _head;
    }
    //插入
    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);
        Span* pre = pos->_pre;
        pre->_next = newSpan;
        newSpan->_pre = pre;
        newSpan->_next = pos;
        pos->_pre = newSpan;
    }
    //消除
    void Erase(Span* pos)
    {
        assert(pos);
        assert(pos != _head);
        Span* pre = pos->_pre;
        Span* next = pos->_next;
        pre->_next = next;
        next->_pre = pre;
    }
    //返回链表头后连接的span
    Span* Begin()
    {
        return _head->_next;
    }
    //返回链表头
    Span* End()
    {
        return _head;
    }
    //链表头后进行插入
    void PushFront(Span* span)
    {
        Insert(Begin(), span);
    }
    //链表头后进行删除
    Span* PopFront()
    {
        Span* ret = Begin();
        Erase(Begin());
        return ret;
    }
    //判断链表头后有无span，无则true，有则false
    bool Empty()
    {
        return _head == _head->_next;
    }
private:
    Span* _head;//链表头span指针
    ObjectPool<Span> _spanPool;//用来实例化span
public:
    std::mutex _mutex;//central cache 的桶锁
};
